package trees;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;

public class BPlusTree<E> {

	/**
	 * Initializes a new BPlusTree of degree n
	 */
	public BPlusTree(int a_n) {
		n = a_n;
		root = new BPlusTreeNode();
		stack = new LinkedList<BPlusTreeNode>();
	}

	/**
	 * Finds the location corresponding to this key within the leaf 
	 * layer of this B+ Tree.  Fills the stack with the path from
	 * the root to this node.
	 */
	private void search(int key) {
		BPlusTreeNode curNode = root;
		stack.clear();
		stack.add(curNode);
		while(!curNode.isLeaf()) {
			if ((curNode = curNode.pickChild(key)) != null)
				stack.addFirst(curNode);
			else
				break;
		}
	}
	
	/**
	 * Inserts this key, value tuple into the tree
	 */
	public boolean insert(int insertKey, E insertValue) {
		BPlusTreeNode curNode;
		/* prepare stack for this insertion */
		search(insertKey);

		curNode = stack.getFirst();
		curNode.insert(insertKey, insertValue);
		return true;
	}
	
	protected class BPlusTreeNode {
		/** Keys that determine the location of children nodes */
		private int[] keys;

		/** Contains child nodes in pointers corresponding to key 
		 * locations */
		private BPlusTreeNode[] children;

		/** If this is a leaf node, then this will contain the 
		 * E elements */
		private E[] leaf;
		
		public BPlusTreeNode() {
			keys = new int[n-1];
			children = (BPlusTreeNode[])Array.newInstance(BPlusTreeNode.class, n);
			leaf = null;
			Arrays.fill(keys, EMPTY);
		}

		/** Returns true iff this node is a leaf node, pointing to
		 * data elements instead of more nodes */
		public boolean isLeaf() {
			boolean isLeaf;
			isLeaf = children == null;
			return isLeaf;
		}

		/**
		 * Returns the child node that corresponds to following a path
		 *  to the target key
		 */
		public BPlusTreeNode pickChild(int target) {
			for (int keyInd = 0; keyInd < n - 1; keyInd ++) {
				if (keys[keyInd] == EMPTY)
					return null;
				if (target <= keys[keyInd])
					return children[keyInd];
			}
			return children[n-1];
		}
		
		public boolean full() {
			for (int key : keys)
				if (key == EMPTY)
					return false;
			return true;
		}
		
		public boolean insert(int key, E value) {
			boolean leaf = isLeaf();
			boolean full = full();
			//TODO implement
			if (leaf && !full) {
				System.out.println();
			} else if (!leaf && !full) {
				System.out.println();
			} else if (!leaf && full) {
				System.out.println();
			}
			return true;
		}

		/** Splits this node and returns the twin containing
		 * the elements for the right half */
		public BPlusTreeNode split() {
			BPlusTreeNode twin = new BPlusTreeNode();
			for (int i = n/2; i < n-1; i ++) {
				twin.keys[i - (n/2)] = keys[i];
				keys[i] = EMPTY;
			}
			return twin;
		}

	}


	/* static variables */
	private static final int EMPTY = Integer.MAX_VALUE;

	/* instance variables */
	/** the stack of the last run search, first element is deepest, last is root */
	private LinkedList<BPlusTreeNode> stack;
	private BPlusTreeNode root;
	private int n;
}
